home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / ESPRESSO.ZIP / PAIR.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-03-14  |  4.5 KB  |  143 lines
  1. #include "espresso.h"
  2.  
  3. /* sf_delcol -- add or delete columns from a set family
  4.  
  5.     if n > 0 then n columns starting from firstcol are deleted
  6.     if n < 0 then n blank columns are inserted starting at firstcol
  7.         (i.e., the first new column number is firstcol)
  8. */
  9. pset_family sf_delcol(A, firstcol, n)
  10. pset_family A;
  11. register int firstcol, n;
  12. {
  13.     register pset p, last, pdest;
  14.     register int i;
  15.     pset_family B;
  16.  
  17.     B = sf_new(A->count, A->sf_size - n);
  18.     foreach_set(A, last, p) {
  19.         pdest = set_clear(GETSET(B, B->count++), B->sf_size);
  20.         for(i = 0; i < firstcol; i++)
  21.             if (is_in_set(p, i))
  22.                 set_insert(pdest, i);
  23.         for(i = n > 0 ? firstcol + n : firstcol; i < A->sf_size; i++)
  24.             if (is_in_set(p, i))
  25.                 set_insert(pdest, i - n);
  26.     }
  27.     sf_free(A);
  28.  
  29.     return B;
  30. }
  31.  
  32.  
  33. pPLA set_pair(PLA)
  34. pPLA PLA;
  35. {
  36.     int i, var, *paired, *oldsiz, oldvar, oldbinvar;
  37.     ppair pair = PLA->pair;
  38.  
  39.     paired = (int *) alloc(cube.num_binary_vars * sizeof(bool));
  40.     for(var = 0; var < cube.num_binary_vars; var++)
  41.         paired[var] = FALSE;
  42.     for(i = 0; i < pair->cnt; i++) {
  43.         if (pair->var1[i] > 0 && pair->var1[i] <= cube.num_binary_vars)
  44.             paired[pair->var1[i]-1] = TRUE;
  45.         else
  46.             fatal("espresso: can only pair binary-valued variables");
  47.         if (pair->var2[i] > 0 && pair->var2[i] <= cube.num_binary_vars)
  48.             paired[pair->var2[i]-1] = TRUE;
  49.         else
  50.             fatal("espresso: can only pair binary-valued variables");
  51.     }
  52.  
  53.     PLA->F = delvar(pairvar(PLA->F, pair), paired);
  54.     PLA->R = delvar(pairvar(PLA->R, pair), paired);
  55.     PLA->D = delvar(pairvar(PLA->D, pair), paired);
  56.  
  57.     /* Now painfully adjust the cube size */
  58.     oldsiz = cube.part_size;
  59.     oldvar = cube.num_vars;
  60.     oldbinvar = cube.num_binary_vars;
  61.  
  62.     cube.num_binary_vars = 0;
  63.     for(var = 0; var < oldbinvar; var++)
  64.         cube.num_binary_vars += (paired[var] == FALSE);
  65.  
  66.     cube.num_vars = oldvar - oldbinvar + cube.num_binary_vars + pair->cnt;
  67.  
  68.     cube.part_size = (int *) alloc(cube.num_vars*sizeof(int));
  69.     for(var = 0; var < pair->cnt; var++)
  70.         cube.part_size[cube.num_binary_vars + var] = 4;
  71.     for(var = 0; var < oldvar-oldbinvar; var++)
  72.         cube.part_size[cube.num_binary_vars + pair->cnt + var] =
  73.             oldsiz[oldbinvar + var];
  74.     cube_setup();
  75.     /* the paired variables should not be sparse (cf. mv_reduce/raise_in)*/
  76.     for(var = 0; var < pair->cnt; var++)
  77.         cube.sparse[cube.num_binary_vars + var] = 0;
  78.     mem_free((char *) paired);
  79. }
  80.  
  81.  
  82. pcover pairvar(A, pair)
  83. pcover A;
  84. ppair pair;
  85. {
  86.     static int lookup[16][4] = {
  87.         0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 
  88.         0,0,0,0, 1,0,0,0, 0,1,0,0, 1,1,0,0,
  89.         0,0,0,0, 0,0,1,0, 0,0,0,1, 0,0,1,1,
  90.         0,0,0,0, 1,0,1,0, 0,1,0,1, 1,1,1,1
  91.     };
  92.     register pcube last, p;
  93.     int insert_col, p1, p2, v1, v2, val, i, pairnum;
  94.  
  95.     insert_col = cube.first_part[cube.num_vars - 1];
  96.  
  97.     /* stretch the cover matrix to make room for the paired variables */
  98.     A = sf_delcol(A, insert_col, -4*pair->cnt);
  99.  
  100.     /* compute the paired values */
  101.     foreach_set(A, last, p)
  102.         for(pairnum = 0; pairnum < pair->cnt; pairnum++) {
  103.             p1 = cube.first_part[pair->var1[pairnum]-1]; 
  104.             p2 = cube.first_part[pair->var2[pairnum]-1];
  105.             v1 = (is_in_set(p, p1+1) != 0)*2 + (is_in_set(p, p1) != 0);
  106.             v2 = (is_in_set(p, p2+1) != 0)*2 + (is_in_set(p, p2) != 0);
  107.             val = v1*4 + v2;
  108.             for(i = 0; i < 4; i++)
  109.                 if (lookup[val][3-i])
  110.                     set_insert(p, insert_col + pairnum*4 + i);
  111.         }
  112.     return A;
  113. }
  114.  
  115.  
  116. /* delvar -- delete variables from A, minimize the number of column shifts */
  117. pcover delvar(A, paired)
  118. pcover A;
  119. bool paired[];
  120. {
  121.     bool run; int first_run, run_length, var, offset = 0;
  122.             
  123.     run = FALSE; run_length = 0;
  124.     for(var = 0; var < cube.num_binary_vars; var++)
  125.         if (paired[var])
  126.             if (run)
  127.                 run_length += cube.part_size[var];
  128.             else {
  129.                 run = TRUE;
  130.                 first_run = cube.first_part[var];
  131.                 run_length = cube.part_size[var];
  132.             }
  133.         else
  134.             if (run) {
  135.                 A = sf_delcol(A, first_run-offset, run_length);
  136.                 run = FALSE;
  137.                 offset += run_length;
  138.             }
  139.     if (run)
  140.         A = sf_delcol(A, first_run-offset, run_length);
  141.     return A;
  142. }
  143.